//实现分块法查找的算法

#include <malloc.h>
#include <stdio.h>

#define MAXTABLE 100     //表中最多的记录个数
#define MAXINDEXTABLE 20 //定义索引表中的最大长度

//索引表类型
typedef struct
{
    int key;        //关键码类型
    int firstIndex; //分块的起始下标
} indexTable[MAXINDEXTABLE];

//顺序表类型
typedef struct
{
    int key;       //关键字数据类型
    char data[10]; //其他数据
} seqList[MAXTABLE];

int IndexSearch(indexTable it, int m, seqList sl, int n, int k)
{
    int low = 0, high = m - 1, mid, count1 = 0;
    printf("二分查找:\n");
    //在索引表中进行二分查找，找到的位置放置low中
    while (low <= high)
    {
        mid = (low + high) / 2;
        printf("第%d次查找,在索引表it[%d,%d]中查找到下标[%d]元素:%d\n", count1 + 1, low, high, mid, it[mid].key);
        if (it[mid].key >= k)
            high = mid - 1;
        else
            low = mid + 1;
        count1++; //累计在索引表中的比较次数
    }
    //在索引表中查找成功后，再在线性表中进行顺序查找
    if (low < m)
    {
        printf("比较%d次,在第%d块中查找到元素%d\n", count1, low + 1, k);
        int count2 = 0;
        int b = n / m; //b为每块的个数

        int i = it[low].firstIndex;
        printf("顺序查找:\n     ");
        while (i < it[low].firstIndex + b - 1 && sl[i].key != k)
        {
            i++;
            count2++;
            printf("%d  ", sl[i].key);
        }
        printf("\n");
        printf("比较%d次，在顺序表中查找元素%d\n", count2, k);
        if (i <= it[low].firstIndex + b - 1)
            return i;
        else
            return -1;
    }
    return -1;
}

int main()
{
    seqList sl;    //查找表
    indexTable it; //索引表
    int n = 25;    //表长
    int k = 46;    //要查询的元素
    int m = 5;     //总块数
    int arr[25] = {8, 14, 6, 9, 10, 22, 34, 18, 19, 31, 40, 38, 54, 66, 46, 71, 78, 68, 80, 85, 100, 94, 88, 96, 87};
    int i;
    // int n = sizeof(arr) / 4;

    //建立查找表
    for (i = 0; i < n; i++)
        sl[i].key = arr[i];
    //建立索引表
    it[0].key = 14;
    it[0].firstIndex = 0;
    it[1].key = 34;
    it[1].firstIndex = 5;
    it[2].key = 66;
    it[2].firstIndex = 10;
    it[3].key = 85;
    it[3].firstIndex = 15;
    it[4].key = 100;
    it[4].firstIndex = 20;

    printf("\n");
    if ((i = IndexSearch(it, m, sl, n, k)) != -1)
        printf("元素%d的位置是%d\n", k, i);
    else
        printf("\n元素 %d不在表中.\n", k);
    printf("\n");
    return 0;
}